package com.company;

import java.util.Arrays;
import java.util.List;
import java.util.Locale;

/**
 * @author shencaobo
 * 动态规划，要找状态变化方程
 * 「经验解法」，同时会掌握 DP 求解的五个核心问题该如何思考。
 * 这五个问题分别是：
 * 如何确定可以使用动态规划来求解问题
 * 如何确定本题的状态定义
 * 如何确定状态转移方程
 * 对状态转移的要求是什么
 * 如何分析动态规划的时间复杂度
 */
public class SolutionDp {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                } else if (i > 0) {
                    dp[i][j] = dp[i - 1][j];
                } else if (j > 0) {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }

        return dp[m - 1][n - 1];
    }


    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else if (i > 0 && j > 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                } else if (i > 0) {
                    dp[i][j] = dp[i - 1][j];
                } else if (j > 0) {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }

        return dp[m - 1][n - 1];
    }


    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                } else if (i > 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                } else if (j > 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        int n = triangle.get(triangle.size() - 1).size();
        int[][] dp = new int[m][n];

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                if (i == 0 && j == 0) {
                    dp[0][0] = triangle.get(0).get(0);
                } else if (i > 0 && j > 0) {
                    //还有种写法，是把上一行的这个位置，设置为最大值
                    if (j == triangle.get(i).size() - 1) {
                        dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
                    } else {
                        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
                    }
                } else if (i > 0) {
                    dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j);
                }
                soutInt(dp);
                if (i == m - 1) {
                    min = Math.min(min, dp[i][j]);
                }
            }
        }

        return min;
    }

    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    dp[i][j] = matrix[i][j];
                } else if (i > 0 && j == 0) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j];
                } else if (i > 0 && j > 0) {
                    if (j == n - 1) {
                        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + matrix[i][j];
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i][j];
                    }
                }
                if (i == m - 1) {
                    min = Math.min(dp[i][j], min);
                }
            }
        }
        return min;
    }

    public int minFallingPathSumTwo(int[][] arr) {
        int m = arr.length;
        int[][] dp = new int[m][m];
        int min = Integer.MAX_VALUE;

        //记录上一行的最小值
        int i1 = -1, i2 = -1;
        for (int i = 0; i < m; i++) {
            //记录当前行的最小值
            int j1 = -1, j2 = -1;
            for (int j = 0; j < m; j++) {
                if (i == 0) {
                    dp[i][j] = arr[i][j];
                } else if (i > 0) {
                    if (j == i1) {
                        //getMinDp(i - 1, j, dp);
                        dp[i][j] = arr[i][j] + dp[i - 1][i2];
                    } else {
                        dp[i][j] = arr[i][j] + dp[i - 1][i1];
                    }
                }

                // 更新 j1 和 j2
                if (dp[i][j] < (j1 == -1 ? Integer.MAX_VALUE : dp[i][j1])) {
                    j2 = j1;
                    j1 = j;
                } else if (dp[i][j] < (j2 == -1 ? Integer.MAX_VALUE : dp[i][j2])) {
                    j2 = j;
                }

                if (i == m - 1) {
                    min = Math.min(dp[i][j], min);
                }
                soutInt(dp);
            }
            i1 = j1;
            i2 = j2;
        }
        return min;
    }

    public int getMinDp(int i, int j, int[][] dp) {
        int min = Integer.MAX_VALUE;
        for (int k = 0; k < dp.length; k++) {
            if (k != j) {
                min = Math.min(min, dp[i][k]);
            }
        }
        return min;
    }


    int[][] cache;
    int mod = 1000000007;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        int n = locations.length;
        cache = new int[n][fuel + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }
        soutInt(cache);
        return dfs(locations, start, finish, fuel);
    }

    /**
     * 计算「路径数量」
     *
     * @param ls    入参 locations
     * @param start 当前所在位置（ls 的下标）
     * @param end   目标哦位置（ls 的下标）
     * @param fuel  剩余油量
     * @return 在位置 u 出发，油量为 fuel 的前提下，到达 end 的「路径数量」
     */
    int dfs(int[] ls, int start, int end, int fuel) {
        // 如果缓存器中已经有答案，直接返回
        // 结束都一样，存的是（开始位置，剩余油量）走过了就直接返回
        if (cache[start][fuel] != -1) {
            return cache[start][fuel];
        }
        int n = ls.length;

        // 如果一步到达不了，说明从位置 u 不能到达 end 位置
        // 将结果 0 写入缓存器并返回
        int need = Math.abs(ls[start] - ls[end]);
        if (need > fuel) {
            cache[start][fuel] = 0;
            return 0;
        }

        // // base case 1：如果油量为 0，且不在目标位置
        // // 将结果 0 写入缓存器并返回
        // if (fuel == 0 && start != end) {
        //     cache[start][fuel] = 0;
        //     return 0;
        // }
        // // base case 2：油量不为 0，且无法到达任何位置
        // // 将结果 0 写入缓存器并返回
        // boolean hasNext = false;
        // for (int i = 0; i < n; i++) {
        //     if (i != start) {
        //         int need = Math.abs(ls[start] - ls[i]);
        //         if (fuel >= need) {
        //             hasNext = true;
        //             break;
        //         }
        //     }
        // }
        // if (fuel != 0 && !hasNext) {
        //     cache[start][fuel] = start == end ? 1 : 0;
        //     return cache[start][fuel];
        // }
        // 计算油量为 fuel，从位置 u 到 end 的路径数量
        // 由于每个点都可以经过多次，如果 u = end，那么本身就算一条路径
        int sum = start == end ? 1 : 0;
        for (int i = 0; i < n; i++) {
            if (i != start) {
                need = Math.abs(ls[i] - ls[start]);
                if (fuel >= need) {
                    sum += dfs(ls, i, end, fuel - need);
                    sum %= mod;
                }
            }
        }
        cache[start][fuel] = sum;
        return sum;
    }

    public int countRoutesBugs(int[] locations, int start, int finish, int fuel) {
        int n = locations.length;
        cache = new int[n][fuel + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }
        return dfsBugs(locations, start, finish, fuel);
    }

    public int dfsBugs(int[] locations, int start, int finish, int fuel) {
        //base case
        if (cache[start][fuel] != -1) {
            return cache[start][fuel];
        }

        if (Math.abs(locations[finish] - locations[start]) > fuel) {
            cache[start][fuel] = 0;
            return 0;
        }

        int sum = start == finish ? 1 : 0;
        int n = locations.length;
        for (int i = 0; i < n; i++) {
            if (i != start) {
                int need = fuel - Math.abs(locations[i] - locations[start]);
                if (need >= 0) {
                    sum += dfsBugs(locations, i, finish, need);
                    sum %= mod;
                }
            }
        }
        cache[start][fuel] = sum;
        return sum;
        // // 如果缓存器中已经有答案，直接返回
        // if (cache[u][fuel] != -1) {
        //     return cache[u][fuel];
        // }
        //
        // int n = ls.length;
        // // base case 1：如果油量为 0，且不在目标位置
        // // 将结果 0 写入缓存器并返回
        // if (fuel == 0 && u != end) {
        //     cache[u][fuel] = 0;
        //     return 0;
        // }
        //
        // // base case 2：油量不为 0，且无法到达任何位置
        // // 将结果 0 写入缓存器并返回
        // boolean hasNext = false;
        // for (int i = 0; i < n; i++) {
        //     if (i != u) {
        //         int need = Math.abs(ls[u] - ls[i]);
        //         if (fuel >= need) {
        //             hasNext = true;
        //             break;
        //         }
        //     }
        // }
        // if (fuel != 0 && !hasNext) {
        //     cache[u][fuel] = u == end ? 1 : 0;
        //     return cache[u][fuel];
        // }
        //
        // // 计算油量为 fuel，从位置 u 到 end 的路径数量
        // // 由于每个点都可以经过多次，如果 u = end，那么本身就算一条路径
        // int sum = u == end ? 1 : 0;
        // for (int i = 0; i < n; i++) {
        //     if (i != u) {
        //         int need = Math.abs(ls[i] - ls[u]);
        //         if (fuel >= need) {
        //             sum += dfs(ls, i, end, fuel - need);
        //             sum %= mod;
        //         }
        //     }
        // }
        // cache[u][fuel] = sum;
        // return sum;


    }

    // int[][] cache;
    // int mod = 1000000007;
    public int countRoutesThree(int[] ls, int start, int finish, int fuel) {
        int n = ls.length;
        int[][] f = new int[n][fuel + 1];
        for (int i = 0; i <= fuel; i++) {
            f[finish][i] = 1;
        }
        // 从状态转移方程可以发现 f[i][fuel]=f[i][fuel]+f[k][fuel-need]
        // 在计算 f[i][fuel] 的时候依赖于 f[k][fuel-need]
        // 其中 i 和 k 并无严格的大小关系
        // 而 fuel 和 fuel-need 具有严格大小关系：fuel >= fuel-need
        // 因此需要先从小到大枚举油量
        for (int cur = 0; cur <= fuel; cur++) {
            for (int i = 0; i < n; i++) {
                for (int k = 0; k < n; k++) {
                    if (i != k) {
                        int need = Math.abs(ls[i] - ls[k]);
                        if (cur >= need) {
                            f[i][cur] += f[k][cur - need];
                            f[i][cur] %= mod;
                        }
                    }
                }
            }
        }
        return f[start][fuel];

        // int len = locations.length;
        // cache = new int[len][fuel + 1];
        // for (int i = 0; i < len; i++) {
        //     Arrays.fill(cache[i], -1);
        // }
        //
        // return dfsThree(locations, start, finish, fuel);
    }


    int m, n, N;

    public int findPaths(int _m, int _n, int maxMove, int startRow, int startColumn) {
        m = _m;
        n = _n;
        N = maxMove;

        //m*n  二维数组，对称性
        int[][] f = new int[m * n][N + 1];
        // 初始化边缘格子的路径数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    add(i, j, f);
                }
                if (i == m - 1) {
                    add(i, j, f);
                }
                if (j == 0) {
                    add(i, j, f);
                }
                if (j == n - 1) {
                    add(i, j, f);
                }
            }
        }
        // 定义可移动的四个方向
        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        // 从小到大枚举「可移动步数」
        for (int step = 1; step <= N; step++) {
            // 枚举所有的「位置」
            for (int k = 0; k < m * n; k++) {
                int x = parseIdx(k)[0], y = parseIdx(k)[1];
                for (int[] d : dirs) {
                    int nx = x + d[0], ny = y + d[1];
                    // 如果位置有「相邻格子」，则「相邻格子」参与状态转移
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                        f[k][step] += f[getIndex(nx, ny)][step - 1];
                        f[k][step] %= mod;
                    }
                }
            }
        }

        // 最终结果为从起始点触发，最大移动步数不超 N 的路径数量
        return f[getIndex(startRow, startColumn)][N];

    }


    // 为每个「边缘」格子，添加一条路径
    void add(int x, int y, int[][] f) {
        int idx = getIndex(x, y);
        for (int step = 1; step <= N; step++) {
            f[idx][step]++;
        }
    }

    // 将 (x, y) 转换为 index
    int getIndex(int x, int y) {
        return x * n + y;
    }

    // 将 index 解析回 (x, y)
    int[] parseIdx(int idx) {
        return new int[]{idx / n, idx % n};
    }



    public void soutInt(int[][] dp) {
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println(" ");
        }
        System.out.println(" ");
    }
}
